\documentclass[a4paper,10pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage{ngerman}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{a4wide} %Kleinere Seitenränder

%opening
\title{1. Übungsrunde\\Statistische Mustererkennung LU}
\author{Weingant Michaela\\Wolf-Dieter Vogl}

\begin{document}

\maketitle

\section{Aufgabe UE-1}
Das Lernverfahren des Perzeptrons wird durch einen Online Training Algorithmus realisiert. Jeder Datenpunkt wird auf seine richtige Klassifizierung untersucht, bei falscher Klassifizierung wird der Gewichtsvektor sofort angepasst. Dieser Vorgang wird solange wiederholt, bis alle Datenpunkte richtig klassifiziert wurden, oder die Maximalanzahl an Iterationen erreicht wurde. 

Ob ein Datenpunkt richtig klassifiziert wurde, erfolgt durch eine Überprüfung, auf welcher Seite der Hyperebene er sich befindet. Die Hyperebene wird durch den Gewichtsvektor $\mathbf{w}$ definiert und steht normal auf diesen Vektor. Durch Multiplikation der Punkte mit dem Klassenlabel $y_i \in {-1,1}$ werden die Punkte mit negativen Klassenlabel auf die positive Halbebene projiziert. Es muss nur mehr überprüft werden, ob der Datenpunkt auf der positiven Seite der Entscheidungsebene liegt, unabhängig vom Klassenlabel (Eqn. \ref{eqn:ue_1_1_verify}). 
\begin{equation}
 \mathbf{w}^T (\mathbf{x}_i)y_i \leq 0 \text{ (falsch klassifizierter Datenpunkt i)} \label{eqn:ue_1_1_verify} 
\end{equation}
Falsch klassifizierte Datenpunkte werden zum Gewichtsvektor $\mathbf{w}$ dazuaddiert, dieser bewegt sich also in Richtung des Datenpunktes (Eqn. \ref{eqn:ue_1_1_train}) und die Entscheidungsgrenze ändert sich auch entsprechend.
\begin{equation}
 \mathbf{w} \leftarrow \mathbf{w} + \gamma \mathbf{x}_i y_i \label{eqn:ue_1_1_train}
\end{equation} 

\subsection{Implementierung}
Der Online Perceptron Lernalgorithmus ist in der Funktion \textit{perco} implementiert. Die Daten werden nicht homogenisiert übergeben, die homogenisierung erfolgt erst in der Funktion durch das hinzufügen einer Spalte mit Einsen zum Anfang der Datenmatrix. Als weiteren Parameter wird die maximale Anzahl an Iterationen angegeben. Als Rückgabewert erhält man den Gewichtsvektor \textbf{w}, in homogenisierter Form, wobei der erste Eintrag des Vektors den Bias $-\varTheta$ beinhaltet. Weiters wird die Anzahl der benötigten Iterationen bis zur Terminierung zurückgegeben. Dieser Wert ist gleich der maximalen Anzahl an Iterationen, wenn der Lernalgorithmus bis zu dieser Anzahl nicht terminiert ist. 

Das Training selbst erfolgt ``klassisch'' im Online Verfahren nach den oben angeführten Formeln. In einer Iteration wird jeder Datenpunkt überprüft, ob er richtig klassifiziert wird. Jeder falsch klassifizierte Datenpunkt (Eqn. \ref{eqn:ue_1_1_verify}) bewirkt eine Addition zum Gewichtsvektor (Eqn. \ref{eqn:ue_1_1_train}). Wurden alle Datenpunkte betrachtet, beginnt die nächste Iteration. 
Als Abbruchbedingung gilt entweder die maximale Anzahl an Iterationen oder es wird abgebrochen, wenn in einer Iteration alle Datenpunkte richtig klassifiziert wurden. 

\subsection{Aufgabe UE-1.1}
 Der Perzeptron Algorithmus terminiert für jedes linear separierbare Trainingsset, jedoch nicht für nicht-linear separierbare Trainingsdaten. Die Probleme OR und AND sind linear separierbar und das Perzeptron terminiert. Beim XOR Problem wird nach der maximalen Anzahl an Iterationen abgebrochen. Das XOR Problem ist nicht linear separierbar (siehe Fig. \ref{fig:ue_1_1_ANDORXOR}).  

\begin{figure}[h]
 \centering
 \includegraphics[width=.3\textwidth]{./images/and}
 \includegraphics[width=.3\textwidth]{./images/or}
 \includegraphics[width=.3\textwidth]{./images/xor}

 \caption{AND, OR und XOR Problem. Die Entscheidungsgrenze (rot) und der Gewichtsvektor (magenta) nach dem Training sind bei AND und OR dargestellt.}
 \label{fig:ue_1_1_ANDORXOR}
\end{figure}

\subsection{Aufgabe UE-1.2}
Die Datenpunkte mit den Klassenlabels \textit{perceptrontarget1} sind linear separierbar, die \textit{perceptrontarget2} sind nicht linear separierbar. 
Die Abbildungen in Figur \ref{fig:ue_1_2_t1} zeigen den Gewichtsvektor und die Entscheidungsgrenze nach einer gewissen Anzahl an Iterationen für \textit{perceptrontarget1}. Nach 9 Iterationen terminiert der Algorithmus und eine Entscheidungsgrenze ist gefunden. 
\begin{figure}[h]
 \centering
 \includegraphics[width=.3\textwidth]{./images/train_iter_1}
 \includegraphics[width=.3\textwidth]{./images/train_iter_5}
 \includegraphics[width=.3\textwidth]{./images/train_iter_9}

 \caption[]{Die Entscheidungsgrenze (rot) und der Gewichtsvektor (magenta) nach 1, 5 und 9 Iterationen für Klassenlabels \textit{perceptrontarget1}.}
 \label{fig:ue_1_2_t1}
\end{figure}

In Abbildung \ref{fig:ue_1_2_t2} werden auch der Gewichtsvektor und die Entscheidungsgrenze abgebildet, aber selbst nach 1000 Iterationen ist noch keine Entscheidungsgrenze gefunden, bei der alle Punkte richtig klassifiziert sind. Da die Punkte nicht linear separierbar sind, kann diese Entscheidungsgrenze auch nicht mit dem Perzeptron Algorithmus gefunden werden. 

\begin{figure}[h]
 \centering
 \includegraphics[width=.3\textwidth]{./images/train2_iter_1}
 \includegraphics[width=.3\textwidth]{./images/train2_iter_500}
 \includegraphics[width=.3\textwidth]{./images/train2_iter_1000}

 \caption[]{Die Entscheidungsgrenze (rot) und der Gewichtsvektor (magenta) nach 1, 500 und 1000 Iterationen für Klassenlabels \textit{perceptrontarget2}.}
 \label{fig:ue_1_2_t2}
\end{figure}

\newpage
\section{Aufgabe UE-2}
Das Ziel der zweiten Aufgabe ist es, den wahren Mittelwert der Verteilung durch die generierten Stichproben zu schätzen. Dabei soll betrachtet werden, welchen Einfluß der Stichprobenumfang auf das Ergebnis hat. 
Wie schätzt man den Mittelwert-Parameter?
Man muss hier drei Konzepte unterscheiden:
\begin{description}
 \item[$\mu$ - ``Estimand'':]  Das ist DIE Wahrheit, die ich suche, und die ich mir anhand der Stichproben errechnen möchte.
 \item[$\hat{\mu}$ - ``Estimator'':] Der Schätzer sagt mir, wie ich aus einer Stichprobe zu einer Parameterschätzung komme: Ich summiere alle Werte der gemessenen Proben und dividiere sie durch die Anzahl der gemessenen Proben.
Der Mittelwert-Schätzer ist als Funktion von Zufallsvariablen selbst eine Zufallsvariable. Dieser Schätzer hat also auch Parameter (Mittelwert, Varianz), die bestimmt werden können (Das könnte man bei einem Skalar nicht).
\item[$\hat{m}$ - ``Estimate'':] Die konkrete Schätzung anhand einer Stichprobe. Wenn ich eine konkrete Stichprobe habe, also wenn ich n mal in mein Datenset hinein messe, und dann den Schätzer auf die gewonnenen Daten anwende, dann bekomme ich die Schätzung.
\end{description}
In der Fachliteratur ist die Unterscheidung nicht immer klar durchgeführt. Das $\mu$  wollen wir schätzen, das  $\hat{\mu}$ entsteht durch Messungen. 

Der Erwartungswert unseres Schätzers ist ein linearer Operator. Wenn ich meinen Schätzer hernehme und als Zufallsvariable betrachte und unendlich oft Stichproben nehme, mir den Wert anschaue und notiere, dann ist im Limit das Mittel dieser Werte gleich $\mu$. Der Erwartungswert des Schätzers ist der Parameter, den ich suche. Wir setzen voraus, dass der Schätzer erwartungstreu ist und keinen Bias aufweist. In unserem Fall ist das auf jeden Fall die korrekte Vorgehensweise, da wir die das Datenset selbst generiert haben und daher sicherlich keine Kalibrierung eines Offsets notwendig ist. 

Die Varianz des Schätzers hängt von der Größe der Stichprobe ab. Sie wird geringer je größer die Stichprobe ist, und fällt mit 1/N (N=Stichprobenumfang).
Selbst wenn man keinen Bias hat, kann sich die Qualität der Schätzer in der Varianz unterscheiden. Man will das $\mu$ bestimmen und hat eine Stichprobe, die einen auf eine Schätzung bringt. Man kann nicht unendlich viele Stichproben machen und auswerten, möchte mit der Schätzung aber trotzdem möglichst nahe am wahren Wert liegen. Wenn man eine breite Varianz hat, dann scheint ein entfernt liegender Schätzer plötzlich sehr wahrscheinlich. Deshalb soll der Schätzer sowohl erwartungstreu sein, als auch eine kleine Varianz haben.  
Wenn eine unendliche große Stichprobengröße vorliegt, ist die Varianz ihrerseits unendlich klein. 
Die Varianz gibt also Aussage darüber, wie nahe die Schätzung am wahren Wert liegt. 

Wie bereits ausgeführt, ist der geschätzte Mittelwert das, was wir erhalten, wenn wir die vorhandenen Verteilung anhand von Stichproben ``ausmessen''. Bei Entnahme einer Zufallsstichprobe kann man anhand der Populationswerte den geschätzten Mittelwert, ``Schätzer'', rechnerisch über die Formel 
$\hat{\mu}=\frac{1}{N}\sum_{i=1}^N X_i$ 
ermitteln. In unserem Fall berechnen wir den geschätzten Mittelwert anhand von mehreren Zufallsstichproben (``Samples'') eines gewissen Umfangs. Der Mittelwert eines jeden Samples selbst ist $\hat{m}$. So wird je 100 Mal eine Schätzung $\hat{m}$ des Mittelwertes bei einer bestimmten Samplegröße erzeugt. Diese 100 Schätzungen zeigen wir in einem Histogramm an und könnten nun wiederum hiervon den Schätzer $\hat{\mu}$ berechnen. Dieser Schätzer ist seinerseits eine Zufallsvariable, welche die Parameter Mittelwert und Varianz aufweist. 

\subsection{Implementierung}
Wir haben die Aufgabe folgendermaßen implementiert: Zuerst wurde ein Set von normalverteilten Werten erstellt. Dies lässt sich in Matlab anhand der Funktion \textit{normrnd} ausführen. Die Anzahl der generierten Werte in diesem Set haben wir mit 50.000 Werten 100 mal so groß gewählt wie der größte Stichprobenumfang, damit wir durch diesen Schritt die eigentliche Aufgabe nicht beeinflussen und auch bei Stichproben mit großem Umfang genügend Werte zur Auswahl stehen. Außerdem kann man mit derart vielen Werten sicherstellen, dass die Normalverteilung möglichst genau wiedergegeben wird. 
Die von uns generierte Zufallsvariable ist diskret, da sie nur endlich viele verschiedene Werte annehmen kann – nämlich nur die Werte ganzer Zahlen. 
Wir machen in unserem Programm 400 Stichproben dieses Sets – jeweils 100 für einen Sampleumfang, welcher 5, 30, 100 und 500 Werte umfasst. Das bedeutet, wir erzeugen u.a. 100 Stichproben, bei denen wir nur 5 Werte herausgreifen. Das soll so deutlich erwähnt sein, weil unter ``Stichprobe'' landläufig verstanden wird, dass man EIN Mal ``hineingreift''.
In dieser Aufgabenstellung erfolgen die Stichproben gewissermaßen nach dem Prinzip ``mit Zurücklegen'' – die zur Verfügung stehenden Werte des Sets werden dadurch nicht weniger oder geändert, da wir sie nur anschauen, nicht entfernen.  
Man kann davon ausgehen, dass eine Stichprobe mit nur 5 Zufallswerten die Verteilung (auch ``Verteilungsfunktion'') kaum bis schlecht repräsentiert, eine mit 500 jedoch schon wesentlich besser. Im umgesetzten Programm werden also von den Stichproben ihrerseits die Mittelwerte und Varianzen berechnet. MATLAB bietet hierzu die Funktionen \textit{mean} und \textit{var} an. Der Mittelwert und die Varianz der generierten Verteilung sind uns bekannt, da beides Erstellungsparameter für die Funktion \textit{normrnd} sind. So lassen sich nun leicht die von den Stichproben errechneten Parameter mit den ``richtigen'' vergleichen. 
Laut Aufgabenstellung werden die geschätzten Mittelwerte $\hat{\mu}$ der 100 Stichproben aller Sampleumfänge errechnet und in einem Histogramm angezeigt. Ein Histogramm summiert alle Werte innerhalb eines bestimmten Intervalls und zeigt diese in Balkenform an. In unserem Fall repräsentieren die Histogramme die erhaltenen Verteilungen ohne Darstellungsverlust (wie es bei einem Histogramm einer kontinuierlichen Verteilung der Fall wäre), da unsere Zufallsvariable sowieso diskret ist und nur die auf der x-Achse gegebenen Werte annehmen kann. 

Wie bereits erwähnt ist es gut, wenn die Varianz des Schätzers gering ausfällt, da das bedeutet, dass der Schätzer nahe an der Wahrheit liegt. Die Varianz kann man grob als die Breite der Verteilung im Histogramm erkennen. Es zeigt sich deutlich, wie man in Abbildung \ref{fig:ue_2_varianz} sieht, dass die Mittelwert-Schätzungen der großen Stichproben eine viel kleinere Varianz aufweisen als die der kleineren Stichproben, und damit mit größerer Wahrscheinlichkeit nahe am tatsächlichen Mittelwert liegen. 

\begin{figure}[h]
 \centering
 \includegraphics[width=\textwidth]{./images/varianz}
 \caption{Histogramm von den Varianzen der Schätzungen.}
 \label{fig:ue_2_varianz}
\end{figure}

Außerdem kann man in Abbildung  \ref{fig:ue_2_mean} vor allem beim kleinsten Stichprobenumfang erkennen, dass der am häufigsten repräsentierte Mittelwert nicht notwendigerweise dem wahren Mittelwert entspricht. Je größer der Stichprobenumfang wird, desto näher liegt der geschätzte Mittelwert am wahren Mittelwert.

\begin{figure}[h]
 \centering
 \includegraphics[width=\textwidth]{./images/mean}
 \caption{Histogramm von den Mittelwerten der Schätzungen.}
 \label{fig:ue_2_mean}
\end{figure}

Augenscheinlich ist der Vergleich der Histogramme mit den tatsächlichen Werten der Parameter Mittelwert und Varianz, da diese in Histogrammform dargestellt nur einen einzigen Balken ergeben würden – jenen im Mittelwert und jenen am Wert der tatsächlichen Varianz.

\end{document}
